#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
    int findNumberOfLIS(vector<int> &nums)
    {
        nums.push_back(INT_MAX);
        vector<int> len(nums.size(), 1);
        vector<int> cnt(nums.size(), 1);
        for (int i = 1; i < nums.size(); i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (nums[j] < nums[i])
                {
                    if (len[j] + 1 > len[i])
                    {
                        len[i] = len[j] + 1;
                        cnt[i] = cnt[j];
                    }
                    else if (len[j] + 1 == len[i])
                    {
                        cnt[i] += cnt[j];
                    }
                }
            }
        }
        return cnt[len.size() - 1];
    }
};
int main()
{
    cout << "Code673" << endl;
    Solution s;
    // vector<int> nums = {1, 3, 5, 4, 7};
    vector<int> nums = {1, 2, 4, 3, 5, 4, 7, 2};
    cout << s.findNumberOfLIS(nums) << endl;
    return 0;
}